Some open problems on cycles

Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-27

Chunhui LAI Mingjing Liu

Abstract： Let f(n) be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. Erd¨os raised the problem of determining f(n). Erd¨os conjectured that there exists a positive constant c such that ex(n, C2k) ≥ cn1+1/k. Haj´os conjecture that every simple even graph on n vertices can be decomposed into at most n/2 cycles. We present the problems, conjectures related to these problems and we summarize the know results. We do not think Haj´os conjecture is true.

YES

 Hits 1679  Downloads 525  Comment